# -*- coding: utf-8 -*-
"""
https://leetcode.cn/problems/climbing-stairs/
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
超时，要用map存一下已经计算过的值，避免重复计算
"""
class Climbing():
    def __init__(self, step):
        # 总的台阶数
        self.step = step
        # 方法数
        self.n = 0

    def climbing(self, steps):
        """
        steps:已经走过的步数
        """
        if steps == self.step:
            self.n = self.n+1
            return
        # 2步以后还在n阶以内就走2步
        if steps+2 <= self.step:
            steps = steps+2
            self.climbing(steps)
            steps = steps-2
        # 走一步
        steps = steps+1
        self.climbing(steps)

a = Climbing(30)
a.climbing(0)
print(a.n)

